//维护一个大顶堆和一个小顶堆
//大顶堆放小于中位数的值，小顶堆放大于中位数的值
    //大顶堆的堆顶就是小的里面最大的，就是中位数左边的数
    //小顶堆的堆顶就是大的里面最小堆，就是中位数右边的数
//如果为奇数，那么大顶堆的个数就比小顶堆的个数多一个，中位数就是大顶堆堆顶元素
//如果为偶数，那么两个堆的元素个数一致，中位数就是两个堆顶的平均值
//同时保证大顶堆的个数 最多比小顶堆的个数多一个
class MedianFinder {
    struct less_cmp
    {
        bool operator() (int a, int b) {return a < b;}
    };
    struct greater_cmp
    {
        bool operator() (int a, int b)  {return a > b;}
    };
    using cmp_t = function<bool(int, int)>;

    void adjustUp(vector<int>& heap, cmp_t cmp)
    {
        int child = heap.size() - 1;
        int parent = (child - 1) / 2;

        while (child > 0)
        {
            if (cmp(heap[parent], heap[child]))
            {
                swap(heap[child], heap[parent]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
                break;
        }
    }
    void adjustDown(vector<int>& heap, int parent, cmp_t cmp)
    {
        int child = parent * 2 + 1;
        while (child < heap.size())
        {
            if (child + 1 < heap.size() && cmp(heap[child], heap[child + 1]))
                child = child + 1;
            
            if (cmp(heap[parent], heap[child]))
            {
                swap(heap[child], heap[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
                break;
        }
    }

    void pop(vector<int>& heap, cmp_t cmp)
    {
        assert(heap.size());
        swap(heap[0], heap[heap.size() - 1]);
        heap.pop_back();
        adjustDown(heap, 0, cmp);
    }

    void push(vector<int>& heap, int num, cmp_t cmp)
    {
        heap.push_back(num);
        adjustUp(heap, cmp);
    }
public:
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        n++;

        //如果新添加的数比大顶堆堆顶（较小数的最大值）小
        //说明这个数一定小于等于中位数，要将它放到大顶堆
        //此时大顶堆的个数可能比小顶堆的个数+1还要多，不满足预设条件
        //要将大顶堆的堆顶放到小顶堆中
        if (bigHeap.size() == 0 || num <= bigHeap[0])
        {
            push(bigHeap, num, less_cmp());

            if (bigHeap.size() > smallHeap.size() + 1)
            {
                push(smallHeap, bigHeap[0], greater_cmp());
                pop(bigHeap, less_cmp());
            }
        }
        //同理
        else
        {
            push(smallHeap, num, greater_cmp());
            if (bigHeap.size() < smallHeap.size())
            {
                push(bigHeap, smallHeap[0], less_cmp());
                pop(smallHeap, greater_cmp());
            }
        }

    }
    
    double findMedian() {
        if (n % 2)
            return bigHeap[0];
        else    
            return (bigHeap[0] + smallHeap[0]) / 2.0;
    }
private:
    vector<int> bigHeap;    //大堆
    vector<int> smallHeap;  //小堆
    int n = 0;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */